using System;
using System.Collections.Generic;
using System.Text;
using ET = ErlyThreads;

namespace Testbed
{
    class Node
    {
        Node
            mLeft = null,
            mRight = null;
        object mValue = null;

        public Node Left  
        { 
            get { return mLeft; } 
            set { mLeft = value;}
        }
        
        public Node Right 
        { 
            get { return mRight; } 
            set { mRight = value; }
        }

        public object Value
        {
            get { return mValue; }
            set { mValue = value; }
        }

        public Node(
            object pValue,
            Node pLeft,
            Node pRight)
        {
            mValue = pValue;
            mLeft = pLeft;
            mRight = pRight;
        }

        public Node() 
        {
        }

        /// <summary>
        /// Builds a binary tree with the specified depth. Value are assigned by 
        /// the callback.
        /// </summary>
        /// <param name="pDepth">The depth of the tree.</param>
        /// <param name="pValBuilderCallback">gives back the value that must be assigned 
        /// to the node</param>
        /// <returns>Binary Tree</returns>
        static public Node BuildTestTree(
            int pDepth,
            Converter<object, object> pValBuilderCallback)
        {
            Node result = new Node();
            result.Value = pValBuilderCallback(Program.NewID());
            if (pDepth > 1)
            {
                result.Left = BuildTestTree(
                    pDepth - 1,
                    pValBuilderCallback);
                result.Right = BuildTestTree(
                    pDepth - 1,
                    pValBuilderCallback);
            }
            return result;
        }

        static public Node BuildRandomContentsTree(
            int pDepth)
        {
            return BuildTestTree(
                pDepth,
                delegate(object cookie)
                {
                    return Guid.NewGuid();
                });
        }
    }

    /// <summary>
    /// my friend tells me that comparing two tree structures for equality is a typical
    /// application of co-routinges, or threading for that matter... lets see if we can
    /// provide an implementation that utilizes the Erly Threads library.
    /// </summary>
    static class TreeCompare
    {
        [Serializable]
        class NewNodeValueMessage
        {
            public NewNodeValueMessage(
                object pSenderId,
                object pValue,
                int pSequenceNumber)
            {
                SenderID = pSenderId;
                Value = pValue;
                SequenceNumber = pSequenceNumber;
            }

            public object SenderID;
            public object Value;
            public int SequenceNumber;


            public delegate NewNodeValueMessage NewNodeCreator(
                object pSender,
                object pValue);
            public NewNodeCreator MakeNewCreator()
            {
                int counter = 0;
                return delegate(
                    object sender,
                    object value)
                    {
                        return new NewNodeValueMessage(
                            sender,
                            value,
                            counter++);
                    };
            }
        }

        [Serializable]
        class ResultMessage
        {
            public ResultMessage(
                bool pIsSame)
            {
                IsSame = pIsSame;
            }
            public bool IsSame;
        }

        [Serializable]
        class PleaseStopYourselfMessage { }

        [Serializable]
        class PleaseStartProcessing 
        {
            public PleaseStartProcessing(
                object pMonitoringThreadID)
            {
                mMonitoringThreadID = pMonitoringThreadID;
            }

            private object mMonitoringThreadID;
            public object MonitoringThreadID
            {
                get { return mMonitoringThreadID; }
                set { mMonitoringThreadID = value; }
            }

        }

        [Serializable]
        class MonitoringThreadThreadIDList
        {
            public MonitoringThreadThreadIDList(
                ICollection<string> pIDList,
                object pMainThreadID)
            {
                IDList = pIDList;
                MainThreadID = pMainThreadID;
            }
            public ICollection<string> IDList;
            public object MainThreadID = null;
        }

        [Serializable]
        class NewNodeValueTerminator 
        {
            public override bool Equals(object obj)
            {
                if (obj.GetType() == typeof(NewNodeValueTerminator))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }

            public override int GetHashCode()
            {
                // hopefull this means use object identity
                // to determine the hashcode
                return base.GetHashCode();
            }
        }

        static public bool AreEqual(
            ICollection<Node> pTrees)
        {
            // the idea is to create as many threads as there are trees
            // then let each thread report on the elements as they are 
            // encountered, back to the checking thread.
            // the checking thread returns a value as soon as it knows it.

            // the contract with the monitoring thread is
            // that this thread will create as many threads as there are
            // trees, and then send it an instruction to begin.
            // the monitoring thread will then kick off the threads 
            // when it is ready for them to start

            string ownID = Program.NewID();
            ET.ProcessRuntime master = new ET.ProcessRuntime(
                ownID);

            List<string> idList = new List<string>();

            foreach (Node tree in pTrees)
            {
                string newID = Program.NewID();
                idList.Add(newID);
                master.InitProcess(
                    newID,
                    delegate(ET.IProcessHandle pThreadBase)
                    {
                        CheckTreeThreadStart(
                            pThreadBase,
                            tree);
                    });
                master.StartProcess(
                    newID);
            }

            // make the monitoring thread
            string monitorThreadID = Program.NewID();
            master.InitProcess(
                monitorThreadID,
                MonitoringThreadStart);
            master.StartProcess(
                monitorThreadID);

            // subscribe to its messages
            // that are not part of the contract
            master.ProcessHandle.SubscribeToMessages(
                monitorThreadID,
                delegate(Type t)
                {
                    if (t == typeof(ET.Messages.ThreadDied) ||
                        t == typeof(ET.Messages.ThreadStopped))
                    {
                        return true;
                    }

                    return false;
                });

            // send the monitor the list of id's to check out
            master.ProcessHandle.SendMessage(
                monitorThreadID,
                new MonitoringThreadThreadIDList(
                    idList,
                    ownID));

            // the result of this function
            // true, tree's are the same
            // false, tree's are not the same
            // will throw if there is another problem
            bool result = true;

            // if the monitoring thread stops before sending a 
            // result message, it is also an error condition
            bool receivedResult = false;

            // wait for the results or the errors
            master.ProcessHandle.WaitForMessages();
            master.ProcessHandle.DispatchQueuedMessages(
                delegate(ET.ReceivedMessage msg)
                {
                    // lets do the errors first
                    if (msg.Message.GetType() == typeof(ET.Messages.ThreadDied))
                    {
                        // we have an error
                        // lets indicate by throwing ;)
                        throw new ApplicationException(
                            "There was a problem with the tree compare function.",
                            (msg.Message as ET.Messages.ThreadDied).Reason);
                    }

                    if (msg.Message.GetType() == typeof(ET.Messages.ThreadStopped))
                    {
                        if (!receivedResult)
                        {
                            throw new ApplicationException(
                                "The monitoring thread stopped before it sent a result message. " +
                                "This is actually a problem");
                        }

                        return;
                    }

                    // now i will state that this condition is also an error
                    // this is also an error!
                    ResultMessage resultFromMonitor = msg.Message as ResultMessage;
                    if (resultFromMonitor != null)
                    {
                        // the result message must come before
                        // any other messages
                        result = resultFromMonitor.IsSame;
                        receivedResult = true;
                        return;
                    }

                    throw new ApplicationException(
                        "The instruction must not reach this line, or somebody screwed up");
                });

            if (!receivedResult)
            {
                throw new ApplicationException(
                    "The algorithm terminated without a result.");
            }

            return result;
        }

        static void CheckTreeThreadStart(
            ET.IProcessHandle pThreadContainer,
            Node pTree)
        {
            // we are essentially going to do a recursive
            // descent here into the tree. if we find a leaf 
            // (ie, a node without both a left and right sub-node)
            // we will "yield" the value of that node to 
            // the monitoring thread.

            // the only other thing to consider is to stop
            // when we receive a message from the monitoring
            // thread when it asks us to

            // wait for the message to start
            // that also tells where to send the update messages

            bool mustQuit = false;
            object monitoringThreadID = null;
            Node treeToCheck = null;
            {
                int messageCounter = 0;

                pThreadContainer.WaitForMessages();
                pThreadContainer.DispatchQueuedMessages(delegate(ET.ReceivedMessage msg)
                {
                    PleaseStartProcessing startMsg =
                        msg.Message as PleaseStartProcessing;

                    // we might actually receive a stop message
                    // before we have event started
                    if (msg == null)
                    {
                        PleaseStopYourselfMessage stopMsg =
                            msg.Message as PleaseStopYourselfMessage;
                        mustQuit = true;
                        return;
                    }

                    #region Some sanity checking on the massages
                    if (msg == null)
                    {
                        throw new ApplicationException(
                            "Received the wrong message for this time.");
                    }

                    // the contract is that this thread only received two
                    // messages in total
                    if (++messageCounter > 2)
                    {
                        throw new ApplicationException(
                            "Received too many messages");
                    }
                    #endregion

                    treeToCheck = pTree;
                    monitoringThreadID = startMsg.MonitoringThreadID;
                });

                // stop without any further ado
                // if we must
                if (mustQuit)
                {
                    return;
                }
            }

            int sequenceNumber = 0;
            Action<object> yield = delegate(object newValue)
            {
                pThreadContainer.SendMessage(
                    monitoringThreadID,
                    new NewNodeValueMessage(
                        pThreadContainer.Id,
                        newValue,
                        ++sequenceNumber));
                // we have yielded a value
                // lets give other thread also a chance to
                // get some work done
                System.Threading.Thread.Sleep(0);

                // lets check for stop messages here
                if (pThreadContainer.NumberOfQueuedMessages > 0)
                {
                    pThreadContainer.DispatchQueuedMessages(
                        delegate(ET.ReceivedMessage msg)
                        {
                            if (msg.Message.GetType() != typeof(PleaseStopYourselfMessage))
                            {
                                throw new ApplicationException(
                                    "Received the wrong message at this time.");
                            }

                            mustQuit = true;
                        });
                }
            };

            Action<Node> recursiveCheck = null;
            recursiveCheck = delegate(Node node)
            {
                if (mustQuit)
                {
                    return;
                }

                // check first if this is a leaf
                if (node.Left != null && node.Right != null)
                {
                    // "yield" the value and return
                    yield(node.Value);
                }

                if (node.Left != null)
                {
                    recursiveCheck(node.Left);
                }

                if (node.Right != null)
                {
                    recursiveCheck(node.Right);
                }
            };

            recursiveCheck(pTree);

        }

        static void MonitoringThreadStart(
            ET.IProcessHandle pThreadContainer)
        {
            ICollection<string> idList = null;
            object mainThreadID = null;

            // wait for a list of id's to monitor
            {
                int messageCounter = 0;
                pThreadContainer.WaitForMessages();
                pThreadContainer.DispatchQueuedMessages(
                    delegate(ET.ReceivedMessage message)
                    {
                        MonitoringThreadThreadIDList expected =
                            message.Message as MonitoringThreadThreadIDList;
                        if (expected == null)
                        {
                            throw new ApplicationException(
                                "Did not get the expected message.\n" +
                                "(In this case, I am the monitoring Thread, " +
                                "and I am waiting on a list of ids of threads to monitor.)");
                        }

                        if (++messageCounter > 1)
                        {
                            throw new ApplicationException(
                                "Got more messages than I bargained on.\n" +
                                "(In this case, I only wanted one message at this stage");
                        }

                        idList = expected.IDList;
                        mainThreadID = expected.MainThreadID;
                    });
            }

            // the list of update messages will go in here,
            // from here they will be checked by the monitoring
            // thread to see if all threads return the same results
            // in the same positions
            Dictionary<string, Dictionary<int, object>> results =
                new Dictionary<string, Dictionary<int, object>>();

            foreach (string id in idList)
            {
                results.Add(
                    id,
                    new Dictionary<int,object>());
                // subscribe to its thread stopped message
                pThreadContainer.SubscribeToMessages(
                    id,
                    delegate(Type t)
                    {
                        if (t == typeof(ET.Messages.ThreadStopped))
                        {
                            return true;
                        }

                        return false;
                    });
                // sent the thread a massage that it can start its processing so long
                pThreadContainer.SendMessage(
                    id,
                    new PleaseStartProcessing(
                        pThreadContainer.Id));
            }

            // 
            Action<PleaseStopYourselfMessage> stopAll = delegate(PleaseStopYourselfMessage msg)
            {
                foreach (string id in idList)
                {
                    pThreadContainer.SendMessage(
                        id,
                        msg);
                }
            };



            int lastCheckedSequnceNumber = 0;
            while (true)
            {
                // if this is true, will check all of the values it has so far
                // to see if we can devine a result yet
                bool scheduleChecking = false;

                pThreadContainer.WaitForMessages();
                pThreadContainer.DispatchQueuedMessages(
                    delegate(ET.ReceivedMessage msg)
                    {
                        // the handlers for these massegs modify the
                        // scheduleChecking variable, to indicate that
                        // the situation has changed in such a way that
                        // it might be prudent to do a check

                        #region One of the threads died unexpectedly
                        {   // One of the computation threads died unexpectedly
                            ET.Messages.ThreadDied dMsg = msg.Message as ET.Messages.ThreadDied;
                            if (dMsg != null)
                            {
                                stopAll(new PleaseStopYourselfMessage());
                                return;
                            }
                        } 
                        #endregion

                        #region Normal "thread found new leaf" message
                        {
                            // received an update on a threads computation
                            NewNodeValueMessage updateMSG = msg.Message as NewNodeValueMessage;
                            if (updateMSG != null)
                            {
                                results[updateMSG.SenderID as string].Add(
                                    updateMSG.SequenceNumber,
                                    updateMSG.Value);
                                scheduleChecking = true;
                                return;
                            }
                        } 
                        #endregion

                        #region Thread finished message
                        {
                            // received a thread stopped message
                            // this means that the tree has been traversed already
                            // for this thread
                            ET.Messages.ThreadStopped stopMSG =
                                msg.Message as ET.Messages.ThreadStopped;
                            if (stopMSG != null)
                            {
                                // find max sequence id
                                int lastID = -1;
                                foreach (int i in results[stopMSG.Id as string].Keys)
                                {
                                    lastID = Math.Max(i, lastID);
                                }
                                lastID++;

                                results[stopMSG.Id as string].Add(
                                    lastID,
                                    new NewNodeValueTerminator());
                                scheduleChecking = true;
                                return;
                            }
                        } 
                        #endregion

                        throw new ApplicationException(
                            "Un unexpected message arrived at the monitoring thread.");
                    });

                if (scheduleChecking)
                {
                    // see if we have sequince number bigger than 
                    // the last one we checked
                    int newSeekingSequenceNr = lastCheckedSequnceNumber + 1;
                    foreach (string id in results.Keys)
                    {
                        int maxSequenceInThread = -1;
                        foreach(int i in results[id].Keys)
                        {
                            maxSequenceInThread = Math.Max(
                                maxSequenceInThread,
                                i);
                        }

                        newSeekingSequenceNr = Math.Min(
                            newSeekingSequenceNr,
                            maxSequenceInThread);
                    }

                    // if all have a bigger number, then we can check the intermediate
                    // values
                    if (newSeekingSequenceNr > lastCheckedSequnceNumber)
                    {
                        for (int i = lastCheckedSequnceNumber + 1 ; i <= newSeekingSequenceNr ; i++)
                        {
                            // lets assume for the sake of brevity, that if all
                            // of the received values for this sequence number is the first,
                            // then they are all the same...

                            // check to see if all the leaf values for a specific
                            // sequence number are the same
                            object firstValue = null;
                            bool areEqual = true;

                            foreach (string id in idList)
                            {
                                // find the first value
                                // then continue on to the others
                                if (firstValue == null)
                                {
                                    firstValue = results[id][i];
                                    continue;
                                }

                                // if the values are !areEqual then
                                // we can terminate early
                                // send the result back to the main/master thread
                                if (!( areEqual &= firstValue.Equals(results[id][i]) ))
                                {
                                    stopAll(new PleaseStopYourselfMessage());
                                    pThreadContainer.SendMessage(
                                        mainThreadID,
                                        new ResultMessage(false));
                                    return;
                                }
                            }

                            // check to see if they have all terminated or not
                            if (areEqual && firstValue.GetType() == 
                                typeof(NewNodeValueTerminator))
                            {
                                pThreadContainer.SendMessage(
                                    mainThreadID,
                                    new ResultMessage(true));
                                return;
                            }
                        }

                        lastCheckedSequnceNumber = newSeekingSequenceNr;
                    }
                }


            }
        }
    }
}
